

// 小于等于MAX_BYTES时，从thread cache中申请内存
// 大于MAX_BYTES时，直接向page cache或者系统堆中申请内存
static const size_t MAX_BYTES = 256 * 1024;

// thread cache和central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;


// 获取内存对象头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;
        _size += 1;
    }

    void* pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = Nextobj(_freeList);
        _size -= 1;

        return obj;
    }

    size_t size() const
    {
        return _size;
    }

    size_t maxSize() const
    {
        return _maxSize;
    }

    bool empty() const
    {
        return _freeList == nullptr;
    }

private:
    void* _freeList = nullptr; 
    size_t _size = 0; 
    size_t _maxSize = 1;
};


// 计算内存对象的对齐和映射规则
class SizeClass
{
public:
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else 
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }
        
        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else 
        {
            alignSize = size;
        }

        return alignSize;
    }

    // 计算自由链表桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else 
        {
            assert(false);
        }

        return -1;
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }

};

#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>

using std::cout;
using std::endl;

// 小于等于MAX_BYTES时，从thread cache中获取内存对象
// 大于MAX_BYTES时，直接从page cache或者系统堆中申请
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache 中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// 获取内存对象的头4/8字节的值，即链接下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}

// 管理还回来的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;
        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);
        _size -= 1;

        return obj;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

    // 设置最大值
    size_t& MaxSize() 
    {
        return _maxSize;
    }
private:
    void* _freeList = nullptr;
    size_t _size = 0; 
    size_t _maxSize = 1;
};


// 计算对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else 
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else 
        {
            alignSize = size;
        }

        return alignSize;
    }

    // 计算自由链表桶对应的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else 
        {
            assert(false);
        }

        return -1;
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else 
        [
            return size / alignNum;
        ]
    }


    // thread cache一次批量向central cache申请内存对象的个数
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size > 0);

        // [0, 512]一次批量申请内存对象的上限值
        // 小对象一次批量申请上限值高
        // 大对象一次批量申请上限值低
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }
};


// Linux系统判断系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr;
    size_t _useCount = 0; // 切好的小块内存被分配给thread cache的计数

    size_t _objSize = 0;  // 切出来的单个对象的大小
    bool _isUse = false;  // 标识是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span();
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    void Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        // 不用delete

        prev->_next = next;
        next->_prev = prev;
    }

    void Push(Span* pos)
    {
        assert(pos);

        Insert(Begin(), pos);
    }

    Span* Pop()
    {
        assert(_head->_next);

        Erase(Begin());
    }

    bool empty() const
    {
        return _head->_next == nullptr;
    }

private:
    Span* _head;

public:
    std::mutex _mtx;
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <map>

using std::cout;
using std::endl;


// 小于等于MAX_BYTES时，从thread cache中申请内存
// 大于MAX_BYTES时，直接从page cache或者系统堆中获取
static const size_t MAX_BYTES = 256 * 1024;

// thread cache和central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page cache
static const size_t NPAGES = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}

// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = nullptr;

        obj = _freeList;
        _freeList = NextObj(_freeList);

        _size -= 1;

        return obj;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;
        
        for(int i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    size_t Size() const
    {
        return _size;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t& MaxSize() 
    {
        return _maxSize;
    }


private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};


// 计算对象的对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 16 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 64 * 1024);
        }
        else
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }

        return alignSize;
    }

    // 计算自由链表桶对应的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else
        {
            assert(false);
        }

        return -1;
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else 
        {
            return size / alignNum;
        }
    }

    // thread cache一次批量申请内存的数量
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2, 512]一次批量申请内存的上限值
        // 小对象一次批量申请的多
        // 大对象一次批量申请的少
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次申请多少页
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = SizeClass::NumMoveSize(size);

        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};


// 验证Linux系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    size_t _useCount = 0; // 分配给thread cache的内存对象的计数
    void* _freeList = nullptr;

    size_t _objSize = 0; // 切出来的单个对象的大小
    bool _isUse = false; // 标识span是否在使用
};  


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span();
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    bool Empty() const
    {
        return _head->_next == nullptr;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    void Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    void PopFront()
    {
        assert(!Empty());

        Erase(Begin());
    }


private:
    Span* _head;

public:
    std::mutex _mtx;
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;


// 小于等于MAX_BYTES时，从thread cache中申请内存
// 大于MAX_BYTES时，直接从page cache中或者系统堆中申请
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page cache
static const size_t NPAGES = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        *((void**)obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = *((void**)_freeList);
        
        _size -= 1;

        return obj;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        *((void**)end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;

        for(size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

    // 设置最大值
    size_t& MaxSize()
    {
        return _maxSize;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};


// 计算对象的对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }

        return alignSize;
    }

    // 计算自由链表桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else
        {
            assert(false);
        }

        return -1;

    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }

    // 一次批量申请内存对象的上限值
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2,512]一次批量申请内存的上限值
        // 小对象一次批量申请的上限值高
        // 大对象一次批量申请的上限值高
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次申请的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = SizeClass::NumMoveSize(size);

        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};


// 验证LINUX系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = ;        // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr;
    size_t _objSize = 0; // 切出来的单个对象的大小

    size_t _useCount = 0;//分配给thread cache内存对象的计数
    bool _isUse = false; // 标记该span是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span();
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        prev->_next = pos;
        pos->_prev = prev;

        pos->_next = newSpan;
        newSpan->_prev = pos;
    }

    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        delete pos;

        prev->_next = next;
        next->_prev = prev;

        return next;
    }

    bool Empty() const
    {
        return _head->_next == nullptr;
    }

    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    Span* PopFront()
    {
        assert(!Empty());

        Span* obj = Begin();

        Erase(Begin());

        return obj;
    }

public:
    Span* _head;

private:
    std::mutex _mtx;
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;


// 小于等于MAX_BYTES时，从thread cache中申请内存
// 大于MAX_BYTES时，直接从page cache或者系统堆中获取
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page  cache 
static const size_t NPAGES = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理还回来的内存对象的自由链表
class FreeList
{
public:
    void Push(void* NextObj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);

        _size -= 1;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;

        for(size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(_freeList);
        NextObj(end) = nullptr;

        _size -= n;
    }

    size_t Size() const
    {
        return _size;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};



// 计算对象的对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }

        return alignSize;
    }

    // 计算对应的自由链表桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + grantpt[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else 
        {
            assert(false);
        }

        return -1;
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignas - 1;
        }
        else
        {
            return size / alignNum;
        }
    }


    // 计算一次批量获取内存对象的数量
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次获取页的数量
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);

        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};



// 计算Linux系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存的数量
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr;
    size_t _objSize = 0; // 切好的单个对象的大小

    size_t _useCount = 0;// 分配给thread cache的内存对象的数量
    bool _isUse = false; // 标识该span是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    bool Empty() const
    {
        return _head->_next == nullptr;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        delete pos;

        prev->_next = next;
        next->_prev = prev;

        return next;
    }

    void PushBack(Span* span)
    {
        assert(span);

        Insert(End(), span);
    }

    Span* PopBack()
    {
        assert(!Empty());

        Span* span = Begin();

        Erase(Begin());

        return span;
    }

private:
    Span* _head;

public:
    std::mutex _mtx; // 桶锁
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;



// 小于等于MAX_BYTES时，从thread cache中申请内存
// 大于MAX_BYTES时，直接从page cache中或者系统堆中申请
static const size_t MAX_BYTES = 256 * 1024;

// thread cache和central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page cache 
static const size_t NPAGES = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理还回来的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);

        _size -= 1;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;

        for(size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};



// 计算对象的对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else 
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }
    }


    // 计算自由链表桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] +group_array[1] + group_array[0];
        }
        else 
        {
            assert(false);
        }

        return -1;
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }


    // 计算一次批量获取内存对象的数量
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2, 512]一次批量获取内存对象的数量
        // 小对象一次批量获取的内存对象上限值高
        // 大对象一次批量获取的内存对象上限值低
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次获取的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);

        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};



// 验证LINUX系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存的起始地址
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr;
    size_t _objSize = 0; // 切出来的单个对象的大小

    size_t _useCount = 0; // 分配给thread cache使用的内存对象
    bool _isUse = false;  // 标识当前的span是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }


    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;

        return next;
    }


    bool Empty() const
    {
        return _head->_next == nullptr;
    }

    void PushFront(Span* pos)
    {
        assert(pos);

        Insert(Begin(), pos);
    }

    Span* PopFront()
    {
        assert(!Empty());

        Span* span = Begin();

        Erase(Begin());

        return span;
    }

private:
    Span* _head;

public:
    std::mutex _mtx;
};



#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;


// 小于等于MAX_BYTES时，总thread cache中申请内存
// 大于MAX_BYTES时，直接从page cache中或者系统堆中申请
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page cache 
static const size_t NPAGES = 129;

//获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = *((void**)_freeList);

        _size -= 1;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        for(int i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }


    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

    size_t& MaxSize()
    {
        return _maxSize;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};



// 计算对象的对齐和映射规则
class SizeClass
{
public:
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else 
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else 
        {
            alignSize = size;
        }

        return alignSize;
    }


    // 计算自由链表桶的数量
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else
        {
            assert(false);
            return -1;
        }
    }   
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else 
        {
            return size / alignNum;
        }
    }

    // 计算一次批量申请内存对象的数量
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2, 512] 一次批量申请内存对象的上限值
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }


    // 计算一次获取的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);
        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
            npage = 1;

        return npage;
    }
        
};


// 验证LINUX系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    size_t _objSize = 0; // 切出来的单个对象的大小
    void* _freeList = nullptr;

    size_t _useCount = 0; // 统计分配给thread cache的内存对象的数量
    bool _isUse = false;  // 标记该span是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;

        return next;
    }

    bool Empty() const
    {
        return head->_next == nullptr;
    }

    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    Span* PopFront()
    {
        assert(!Empty());

        Span* span = Begin();
        Erase(Begin());

        return span;
    }

private:
    Span* _head;

public:
    std::mutex _mtx;
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstdlib>

using std::cout;
using std::endl;


// 定长内存池 - 申请和释放固定大小的内存对象
template<class T>
class ObjectPool
{
public:
    T* New()
    {
        T* obj = nullptr;

        if(_freeList)
        {
            obj = (T*)_freeList;
            _freeList = *((void**)_freeList);
        }
        else
        {
            size_t objSize = sizeof(T) < sizeof(void*) : sizeof(void*) : sizeof(T);

            if(_leftBytes < objSize)
            {
                _leftBytes = 128 * 1024;

                _memory = (char*)malloc(_leftBytes);

                if(nullptr == _memory)
                {
                    throw std::bad_alloc();
                }
            }

            obj = (T*)_memory;
            _memory += objSize;
            _leftBytes -= objSize;
        }

        new(obj)T;

        return obj;
    }


    void Delete(T* obj)
    {
        assert(obj);

        obj->~T();

        *((void**)obj) = _freeList;
        _freeList = obj;
    }

private:
    char* _memory = nullptr;
    void* _freeList = nullptr;
    size_t _leftBytes = 0;
};


#include <iostream>
#include <cstdio>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;


// 小于等于MAX_BYTES时，直接从thread cache中申请内存
// 大于MAX_BYTES时，从page cache或者系统堆中申请
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache 中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移 - 8KB - 2^13
static const size_t PAGE_SHIFT = 13;

// page  cache
static const size_t NPAGES  = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        *((void**)obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = *((void**)_freeList);

        _size -= 1;

        return obj;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;

        for(size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    size_t Size() const
    {
        return _size;
    }

    // 设置最大值
    size_t& MaxSize()
    {
        return _maxSize;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};


// 计算对象的对齐和映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t RoundUp(size_t size)
    {
        if(size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if(size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else 
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }

        return -1;
    }
    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum != 0)
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
        else
        {
            alignSize = size;
        }
    }

    // 计算自由链表桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else
        {
            assert(false);
            return -1;
        }
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }

    // 计算一次批量申请内存对象的上限
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2, 512]一次批量申请内存对象的上限值
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }


    // 计算一次获取到的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);

        size_t npage = num * size;

        npage >>= PAGE_SHIFT;

        if(npage == 0)
            npage = 1;

        return npage;
    }
};



// 验证LINUX系统地址总线的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr;
    size_t _objSize = 0; // 切好的单个对象的大小

    size_t _useCount = 0; // 分配给thread cache的内存对象的数量
    bool _isUse = false;  // 标识该span是否在使用
};


// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }


    Span* Begin() 
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    bool Empty() const
    {
        return _head->_next == nullptr;
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        // prev newSpan pos
        prev->_next = newSpan;
        newSpan->_prev = prev;

        newSpan->_next = pos;
        pos->_prev = newSpan;
    }


    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }


    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    void* PopFront()
    {
        assert(!Empty());

        Span* span = Begin();

        Erase(Begin());

        return span;
    }

private:
    Span* _head;

public:
    std::mutex _mtx;
};




// thread cache 一次申请内存空间的上限值
static const size_t MAX_BYTES = 256 * 1024;

// thread cache 和 central cache 中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移
static const size_t PAGE_SHIFT = 13;

// page cache 中page 链表桶的数量
static const size_t NPAGES = 129;


// 获取内存对象的下一个对象的地址，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    assert(obj);

    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);

        _size -= 1;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;
        size_t i = 0;

        while(i < n - 1 && NetxObj(end) != nullptr)
        {
            i++;
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

    size_t& maxSize()
    {
        return _maxSize;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};


// 计算对象的对齐和映射规则
class SizeClass 
{
public:
    // 计算对齐后的字节数
    static inline size_t Round(size_t size)
    {
        assert(size <= MAX_BYTES);

        if(size <= 128)
        {
            return _Round(size, 8);
        }
        else if(size <= 1024)
        {
            return _Round(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _Round(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _Round(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _Round(size, 8 * 1024);
        }
        else 
        {
            assert(false);
            return -1;
        }
    }
    static inline size_t _Round(size_t size, size_t alignNum)
    {
        size_t alignSize = 0;

        if(size % alignNum == 0)
        {
            alignSize = size;
        }
        else
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
    }

    // 计算映射到的哈希桶的下标
    static inline size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        static size_t group_array[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + group_array[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group_array[1] + group_array[0];
        }
        else if(size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
        }
        else if(size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else 
        {
            return -1;
        }
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum != 0)
        {
            return size / alignNum;
        }
        else
        {
            return size / alignNum - 1;
        }
    }

    // 计算thread cache一次批量申请内存对象的个数
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2;
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次获取到的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);
        
        size_t npage = num * size;
        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};

// 验证LINUX系统的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0; // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _freeList = nullptr; // 管理切好的内存对象的自由链表
    size_t _useCount = 0; // 该span分配给thread cache使用的内存对象的数量

    size_t _objSize = 0; // 切好的单个对象的大小
    bool _isUse = false; // 标记该span是否正在被使用
};



// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* span)
    {
        assert(pos);
        assert(span);

        Span* prev = pos->_prev;
        // prev pos span
        prev->_next = pos;
        pos->_prev = prev;

        pos->_next = span;
        span->_prev = pos;
    }

    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    Span* PopFront()
    {
        assert(!Empty());

        Span* front = Begin();
        Erase(Begin());

        return front;
    }

    bool Empty()
    {
        return _head->_next == nullptr;
    }

private:
    Span* _head;
};





// 一次向thread cache申请内存空间的上限值
static const size_t MAX_BYTES = 256 * 1024;

// thread cache和central cache 中自由链表桶的数量
static const size_t NFREELISTS = 208;

// 页大小转换偏移
static const size_t PAGE_SHIFT;

// page cache中自由链表中的数量+1
static const size_t NPAGES = 129;


// 获取内存对象的头4/8字节的值，即需要链接的下一个对象的地址
inline void*& NextObj(void* obj)
{
    return *((void**)obj);
}


// 管理切好的内存对象的自由链表
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        NextObj(obj) = _freeList;
        _freeList = obj;

        _size += 1;
    }

    void* Pop()
    {
        assert(_freeList);

        void* obj = _freeList;
        _freeList = NextObj(_freeList);

        _size -= 1;
    }

    void PushRange(void* start, void* end, size_t n)
    {
        assert(start);
        assert(end);

        NextObj(end) = _freeList;
        _freeList = start;

        _size += n;
    }

    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n <= _size);

        start = _freeList;
        end = start;

        for(size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }

        _freeList = NextObj(end);
        NextObj(end) = nullptr;

        _size -= n;
    }

    bool Empty() const
    {
        return _freeList == nullptr;
    }

    size_t Size() const
    {
        return _size;
    }

    size_t& MaxSize()
    {
        return _maxSize;
    }

private:
    void* _freeList = nullptr;
    size_t _size = 0;
    size_t _maxSize = 1;
};




// 计算对象的对其映射规则
class SizeClass
{
public:
    // 计算对齐后的字节数
    static inline size_t Round(size_t size)
    {
        if(size <= 128)
        {
            return _Round(size, 8);
        }
        else if(size <= 1024)
        {
            return _Round(size, 16);
        }
        else if(size <= 8 * 1024)
        {
            return _Round(size, 128);
        }
        else if(size <= 64 * 1024)
        {
            return _Round(size, 1024);
        }
        else if(size <= 256 * 1024)
        {
            return _Round(size, 8 * 1024);
        }
        else 
        {
            assert(false);
            return -1;
        }

    }
    static inline size_t _Round(size_t size, size_t alignNum)
    {   
        size_t alignSize = 0;

        if(size % alignNum == 0)
        {
            alignSize = size;
        }
        else
        {
            alignSize = (size / alignNum + 1) * alignNum;
        }
    }

    // 计算所对应的自由链表桶
    static inline size_t Index(size_t size)
    {
        static int groups[4] = {16, 56, 56, 56};

        if(size <= 128)
        {
            return _Index(size, 8);
        }
        else if(size <= 1024)
        {
            return _Index(size - 128, 16) + groups[0];
        }
        else if(size <= 8 * 1024)
        {
            return _Round(size - 1024, 128) + groups[0] + groups[1];
        }
        else if(size <= 64 * 1024)
        {
            return _Round(size - 8 * 1024, 1024) + groups[0] + groups[1] + groups[2];
        }
        else if(size <= 256 * 1024)
        {
            return _Round(size - 64 * 1024, 8 * 1024) + groups[0] + groups[1] + groups[2] + groups[3];
        }
        else
        {
            return -1;
        }
    }
    static inline size_t _Index(size_t size, size_t alignNum)
    {
        if(size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }

    // 计算一次批量获取到的内存对象的个数
    static inline size_t NumMoveSize(size_t size)
    {
        assert(size <= MAX_BYTES);

        // [2, 512]一次批量获取内存对象的上限
        size_t num = MAX_BYTES / size;

        if(num < 2)
        {
            num = 2; 
        }
        else if(num > 512)
        {
            num = 512;
        }

        return num;
    }

    // 计算一次获取的页数
    static inline size_t NumMovePage(size_t size)
    {
        assert(size <= MAX_BYTES);

        size_t num = NumMoveSize(size);

        size_t npages = num * size;
        npage >>= PAGE_SHIFT;

        if(npage == 0)
        {
            npage = 1;
        }

        return npage;
    }
};


// 验证Linux系统的位数
#ifdef __LP64__
    typedef unsigned long long PAGE_ID;

#elif __linux__
    typedef size_t PAGE_ID;

#endif


// 管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0; // 页的数量

    Span* _prev = nullptr;
    Span* _next = nullptr;

    bool _isUse = false; // 标识当前Span是否在使用
    size_t _useCount = 0;  // 记录当前span分配给thread cache使用的内存对象的数量

    size_t _objSize = 0; // 切好的单个对象的大小
    void* _freeList = nullptr;
};



class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_prev = _head;
        _head->_next = _head;
    }

    Span* Begin()
    {
        return _head->next;
    }

    Span* End()
    {
        return _head;
    }

    void Insert(Span* pos, Span* span)
    {
        assert(pos);
        assert(span);

        Span* prev = pos->_prev;
        // prev pos span
        prev->_next = pos;
        pos->_prev = prev;

        pos->_next = span;
        span->_prev = pos;
    }

    Span* Erase(Span* pos)
    {
        assert(pos);
        assert(pos != End());

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    void PushFront(Span* span)
    {
        assert(span);

        Insert(Begin(), span);
    }

    Span* PopFront()
    {
        assert(!Empty());

        Span* front = Begin();
        Erase(Begin());

        return front;
    }

    bool Empty()
    {
        return _head->_next == nullptr;
    }

private:
    Span* _head;

public:
    std::mutex _mtx;
};



